package 数据结构和算法.算法.排序算法.快速排序;

import java.util.Arrays;

/**
 * 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：
 * 通过一趟排序将要排序的数据分割成独立的两部分，
 * 其中一部分的所有数据都比另外一部分的所有数据都要小，
 * 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行
 */

public class QuickSort {
    public static void main(String[] args) {
        /*int[][] arrays = {
                {1, 2, 8, 9},
                {2, 4, 9, 12},
                {4, 7, 10, 13},
                {6, 8, 11, 15}
        };
        int[] arraya = arrays[1];
        System.out.printf(Arrays.toString(arraya));
        ;
        System.out.printf(String.valueOf(arrays.length));*/

        int[] array = {2, 5, 1, 3, 0, 8, 9, 0, 3, 5, 7, 8, 9, 1, 2, 4, 5, 1, 2, 4, 7, 9};
        sort(array, 0, array.length - 1);
        System.out.printf(Arrays.toString(array));
    }

    public static void sort(int[] array, int L, int R) {
        int i = L;
        int j = R;
        int rulcrum = array[(L + R) / 2];
        while (i <= j) {
            while (rulcrum > array[i]) {
                i++;
            }

            while (rulcrum < array[j]) {
                j--;
            }

            if (i <= j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                j--;
                i++;
            }
        }

        if (L < j) {
            sort(array, L, j);
        }

        if (i < R) {
            sort(array, i, R);
        }
    }
}
